package com.berchen.算法.查找;

import java.util.Arrays;

/**
 * 菲波那契查找
 * 菲波那契数列
 * 菲波那契查找和二分查找差不多 只不过就是mid的计算方法？
 * 如何计算mid?
 */
public class FibonacciSearch {

    private static int size;
    public static void main(String[] args) {
        size=20;
        int arr[] ={1,5,6,9,10,43,54};
        int i = fib(arr,  0);
        System.out.println(i);
    }

    public static int fib(int[] arr, int value){

        int left =0;
        int right=arr.length-1;
        int[] fibArr=fibArr();
        int fibIndex=0;
        int mid =0;

        // 找到分割的地方
        while (right>fibArr[fibIndex]-1){
            fibIndex++;
        }

        // 创建数组
        int tempArr[]= Arrays.copyOf(arr,fibArr[fibIndex]);
        for(int i=right+1;i<tempArr.length;i++){
            tempArr[i]=arr[right];
        }

        while (left<=right){
            mid=left+fibArr[fibIndex-1]-1;

            if(value<tempArr[mid]){
                right=mid-1;
                fibIndex--;
            }
            if(value>tempArr[mid]){
                left=mid+1;
                fibIndex-=2;
            }
            if(value==tempArr[mid]){
                if (right<mid){
                    return right;
                }else {
                    return mid;
                }
            }
        }
        return -1;
    }

    public static int[] fibArr(){
        int[] fib=new int[size];
        fib[0]=1;
        fib[1]=1;
        for (int i =2;i<size;i++){
            fib[i]=fib[i-1]+fib[i-2];
        }
        return fib;
    }
}
